#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int QElemType;
typedef int Status;

/*
 * 存储结构
 */
typedef struct QNode {
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct{
    QueuePtr front;    // 队头指针
    QueuePtr rear;    // 队尾指针
} LinkQueue;

//初始化队列
Status InitQueue(LinkQueue *q) {
    q->front = q->rear = (QueuePtr) malloc(sizeof(QNode));
    if (!q->front) {
        //判定是否溢出？
        exit(OVERFLOW);
    }
    q->front->next = NULL;
    return OK;
}

//销毁队列
Status DestroyQueue(LinkQueue *q) {
    while (q->front) {
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }
    return OK;
}  

//清空队列
Status ClearQueue(LinkQueue *q) {
    DestroyQueue(q);
    InitQueue(q);
    return OK;
}

//判定队列是否空
Status IsEmpty(LinkQueue q) {
    if (q.front->next == NULL) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/*
 * 获取队列的长度
 */
int GetLength(LinkQueue Q){
    int i = 0;
    QueuePtr p = Q.front;
    while (Q.rear != p) { 
        // 通过遍历得到队列长度
        i++;
        p = p->next;
    }
    return i;
}

//获取队列头部元素
Status GetHead(LinkQueue Q, QElemType *e) {
    QueuePtr p;
    if (Q.front == Q.rear){
        return ERROR;
    }
    p = Q.front->next;
    *e = p->data;
    return OK;
}

//入队列
Status EnQueue(LinkQueue *q, QElemType e) {
    QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
    if (!p) {
        exit(OVERFLOW);
    }
    p->data = e;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
    return OK;
}

/*
 * 出队
 */
Status DeQueue(LinkQueue *Q, QElemType *e){
    QueuePtr p;
    if (Q->front == Q->rear){
        return ERROR;
    }
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p){
        Q->rear = Q->front;
    }
    free(p);
    return OK;
}

//访问某个元素
void visit(QElemType e) {
    printf("===========================\n");
    printf("element = %d\n", e);
}

//遍历整个队列
Status TraverseQueue(LinkQueue q, void (*visit)(QElemType)) {
    QueuePtr p = q.front->next;
    while (p) {
        visit(p->data);
        p = p->next;
    }
    return OK;
}

int main(){
    LinkQueue Q;
    if (InitQueue(&Q)){
        QElemType e;
        int i;

        printf("Init_success!!\n");

        if (IsEmpty(Q)){
            printf("queue is empty\n");
        }

        for (i = 0; i < 10; i++){
            EnQueue(&Q, i);
        }

        GetHead(Q, &e);
        printf("The first element is %d\n", e);

        printf("length is %d\n", GetLength(Q));

        DeQueue(&Q, &e);
        printf("delete element is %d\n", e);

        TraverseQueue(Q, *visit);

        if (DestroyQueue(&Q)){
            printf("\ndestroy_success\n");
        }
    }
}

